
        <html>
			<head>
			     <title>2015移动安全挑战赛（阿里&amp;看雪主办）全程回顾 - GoSSIP_SJTU</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/5409">http://drops.wooyun.org/tips/5409</a></h1>
				
      <p>
        <p>Author: 上海交通大学密码与计算机安全实验室软件安全小组GoSSIP</p>

<h1>第一题</h1>

<hr />

<h2>0x1 分析</h2>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205093477.jpg" alt="APK界面" /></p>

<!--more-->

<p><a href="http://drops.wooyun.org/wp-content/uploads/2015/03/AliCrackme_1.zip">题目下载</a></p>

<p>本次比赛的第一个题目是一个APK文件，安装后，需要用户输入特定的密码，输入正确会显示破解成功。该题目的APK文件没有太多的保护，可以直接使用各种分析工具（如jeb等）反编译得到Java代码。</p>

<p>获得正确注册码的代码逻辑为： 1. 从logo.png这张图片的偏移89473处，读取一个映射表，768字节编码成UTF-8，即256个中文表 2. 从偏移91265处读取18个字节编码的UTF-8（即6个中文字符）为最终比较的密码。然后通过输入的字符的转换，转换规则就是ASCII字符编码，去比较是否和最终密码相等。</p>

<h2>0x2 巧妙的解法</h2>

<p>我们在这里提供一种非常愉快的解法，不需要复杂的工具和分析，大家可以参见视频</p>

<p><embed src="http://drops.wooyun.org/wp-content/uploads/2015/03/alimobisec_1.mp4" autostart="0" width="480" height="390" >
</embed></p>

<p>打开app后，我们使用adb logcat并加上这个app独有的 <em>lil</em> 标签过滤日志输出，发现app输出日志中有table，pw以及enPassword。随意输入字符串如123456789，发现enPassword中有对应的中文输出，根据输出反馈，可以知道有如下对应关系</p>

<ul>
<li>1 - 么</li>
<li>2 - 广</li>
<li>3 - 亡</li>
<li>4 - 门</li>
<li>5 - 义</li>
<li>6 - 之</li>
<li>7 - 尸</li>
<li>8 - 弓</li>
<li>9 - 己</li>
</ul>

<p>通过观察Logcat输出可知，最终目标pw应为<em>义弓么丸广之</em>，根据上述table中的对应关系，我们可以得到最终密码为：</p>

<pre><code>581026
</code></pre>

<h1>第二题</h1>

<hr />

<h2>0x1 分析</h2>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008351321399.png" alt="APK界面" /></p>

<p><a href="http://drops.wooyun.org/wp-content/uploads/2015/03/AliCrackme_2.zip">题目下载</a></p>

<p>本次比赛的第二个题目仍然是一个独立的APK文件，安装后，需要用户输入特定的密码，输入正确会显示成功。第二题APK在Java层代码中并没有关键逻辑，将用户输入直接传给native so层中<em>securityCheck</em>这个native method（<em>securityCheck</em>方法在libcrackme.so中），由native code来决定返回正确与否。</p>

<p>用IDA工具打开libcrackme.so，首先看下程序的大致流程，可以看到在<em>securityCheck</em>这个方法调用前，在<em>init_array</em>段和<em>JNI_Onload</em>函数里程序都做了些处理，而在<em>securityCheck</em>方法的最后有一个判断，将用户输入和<strong>wojiushidaan</strong>做比较。尝试直接输入<strong>wojiushidaan</strong>，发现密码错误，因此可以猜测前面一大段逻辑的作用就是会把这个最终的字符串改掉。此时的思路是只需知道最终判断时候这个<strong>wojiushidaan</strong>地址上的变换后的值就行了。尝试使用IDA调试发现一旦attach上去，整个程序就退出，想必一定是在之前的代码中有反调试的代码。</p>

<h2>0x2 巧妙的解法</h2>

<p>同上一题一样，我们提供一种非常巧妙的解法：</p>

<p>注意到在最终比较之前，程序使用了<em>android&#95;log&#95;print</em>函数，当我们直接运行程序时，发现这里固定输出了</p>

<pre><code>I/yaotong ( XXX): SecurityCheck Started...
</code></pre>

<p>这时候我们想，是否可以直接patch这个libcrackme.so，修改打印的内容，直接利用这个函数帮我们输出此时真正需要比较的值。</p>

<p>我们选择patch的方法是直接把这个log函数往下移，因为在0x12A4地址处正好有我们需要的打印的数据地址赋值给了R2寄存器（本来是为了给后面做比较用的），因此将代码段从0x1284到0x129C的地方都用NOP改写，在0x12AC的地方调用log函数，同时为了不影响R1的值，把0x12A0处的R1改成R3。</p>

<p>下面是对比patch前和patch后的图：</p>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205025533.png" alt="Patch前代码" /></p>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205193745.png" alt="Patch后代码" /></p>

<p>参考视频给出了完整的解决过程：</p>

<p><embed src="http://static.wooyun.org/drops/20150331/alimobisec_2.mp4" autostart="0" width="480" height="390" >
</embed></p>

<p>通过观察Logcat输出可知，最终密码为：</p>

<pre><code>aiyou,bucuoo
</code></pre>

<h1>第三题</h1>

<hr />

<p><a href="http://drops.wooyun.org/wp-content/uploads/2015/03/AliCrackme_3.zip">题目下载</a></p>

<p>在介绍本次比赛第三道题目之前，首先要介绍一个我们GoSSIP小组开发的基于Dalvik VM的插桩分析框架InDroid，其设计思想是直接修改AOSP上的Dalvik VM解释器，在解释器解释执行Dalvik字节码时，插入监控的代码，这样就可以获取到所有程序运行于Dalvik上的动态信息，如执行的指令、调用的方法信息、参数返回值、各种Java对象的数据等等。InDroid只需要修改AOSP的dalvik vm部分代码，编译之后，可直接将编译生成的新libdvm.so刷入任何AOSP支持的真机设备上（目前我们主要使用Nexus系列机型特别是Nexus4和Galaxy Nexus）。在本次比赛的第三题和第四题分析过程中，我们使用该工具进行分析，大大提高了分析效率。具体细节可以参考我们发表的CIT 2014论文<strong>DIAS: Automated Online Analysis for Android Applications</strong></p>

<p>回到题目上，将第三题的APK进行反编译后发现代码使用了加壳保护，对付这类加壳的APK，最方便的方法就是使用InDroid来进行动态监控，因为静态加密的DEX一定会在执行时在Dalvik上时解密执行，这样我们可以直接在InDroid框架里对解释执行过程中释放出来的指令进行监控。在我们自己使用的工具里，我们开发了一个动态读取整个dex信息的接口，执行时去读DexFile这个结构，然后对其进行解析（解析时直接复用了Android自带的dexdump的代码）。这样，我们的插桩工具在运行程序后，能够直接得到程序的dex信息，同未经保护时使用dexdump后得到的结果基本一致。虽然我们得到的信息是dalvik字节码，没有直接反编译成Java代码那么友好，但由于程序不大，关键逻辑不多，因此对我们的分析效率影响并不大。</p>

<p>使用InDroid进行脱壳的演示视频：</p>

<p><embed src="http://drops.wooyun.org/wp-content/uploads/2015/03/Alimobisec_3_1.mp4" autostart="0" width="480" height="390" >
</embed></p>

<p>在得到脱壳之后的dexdump结果后，我们可以对代码进行静态分析。我们发现用户的输入会传递给继承自Class timertask的Class b，被Class b的<em>run</em>方法处理。在<em>run</em>方法中，如果<em>sendEmptyMessage</em>方法被调用时的参数为0，就会导致Class c的<em>handleMessage</em>这个方法中得到的<em>message</em>的<em>what</em>值为0，进而导致103除0跳入异常处理中，触发成功的提示。</p>

<p>继续分析这个<em>run</em>方法的逻辑，可以知道用户的输入会被传递到Class e的<em>a</em>方法中，做个类似摩尔斯译码的过程（其译码与标准的摩尔斯电码不太一样），然后经过下面一系列大量的混淆用的无用处理和不可能相等的比较后，将译码后得到的字符串送入到关键的判断中去。这个判断成功的条件比较复杂：对于译码后得到的字符串的前两个字节，要求使用hashcode方法的结果等于3618，并且这两个字节相加等于168，才会进入后面的比较。我们穷搜索一下符合这类输入的字符串：</p>

<pre><code>#!java
for ( size_t i = 33; i &lt; 127; ++i )
{
    for ( size_t j = 33; j &lt; 127; ++j )
    {
        String x =String.valueOf((char)j)+String.valueOf((char)i);
        if (x.hashCode()==3618 &amp;&amp; (i+j) == 168)
        {
            System.out.println(x);
            System.out.println(j+i);
        }
    }
}
</code></pre>

<p>输出为：</p>

<pre><code>s5
168
</code></pre>

<p>也就是说只有<strong>s5</strong>满足hashcode为3618，而相加等于168这个条件。</p>

<p>确定前两个字符后，后面还有四个字符需要同Class e和Class a的Annotation值比较。因为我们做脱壳的时候直接使用了dexdump的代码，而dexdump即使到最新版里也无法很好地处理Annotations：</p>

<pre><code>// TODO: Annotations.
</code></pre>

<p>不过没关系，我们还有动态分析工具这一利器，因为最终目的是得到<em>getAnnotation</em>方法的返回值，依然可以用InDroid在Dalvik执行到<em>getAnnotation</em>方法时监控返回值，就能得到Annotation的具体值。使用InDroid获取具体信息的视频如下：</p>

<p><embed src="http://drops.wooyun.org/wp-content/uploads/2015/03/Alimobisec_3_2.mp4" autostart="0" width="480" height="390" >
</embed></p>

<p>最后可知，符合程序需求的字符串是</p>

<pre><code>s57e1p
</code></pre>

<p>使用程序内部的对应表，对其进行逆变换，能够让程序输入成功提示的输入应该是：</p>

<pre><code>… _____ ____. . ..___ .__.
</code></pre>

<h1>第四题</h1>

<hr />

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205167871.png" alt="APK界面" /></p>

<p><a href="http://drops.wooyun.org/wp-content/uploads/2015/03/AliCrackme_4.zip">题目下载</a></p>

<p>本次移动安全挑战赛的第四题和第三题一样，是一个包含了加壳dex的APK文件，我们使用同解决上一题一样的方法，用InDroid得到原始dex文件的dexdump结果:</p>

<p>使用InDroid进行脱壳的演示视频：</p>

<p><embed src="http://drops.wooyun.org/wp-content/uploads/2015/03/Alimobisec_4.mp4" autostart="0" width="480" height="390" >
</embed></p>

<p>Dex整体处理过程和上一题也类似，使用<code>handleMessage</code>处理最后的判断输入成功与否，只有<code>sendEmptyMessage(0)</code>后，触发除以0的异常才能成功。不过这一题将用户输入转成byte后，传给一个native的方法：<code>ali$a</code>的<code>M$j</code>方法，另外参数还包括一个常数48和Handler。看样子逆向native库势在必行了。这一题的lib文件夹下文件和上一题是一样的，有三个文件，其中<code>libmobisecy.so</code>其实是个zip文件，解压后是个classes.dex，直接反汇编后，类和方法的名字都在，只是里面的代码都是</p>

<pre><code>throw new RuntimeException();
</code></pre>

<p>而<code>libmobisecz.so</code>直接就是一堆binary数据，猜测应该是运行时会被解密，通过某种方式映射到为真正的代码执行。因此我们的目标就是<code>libmobisec.so</code>这个ELF文件。</p>

<p>直接用IDA打开<code>libmobisec.so</code>，发现IDA会崩溃。用readelf发现正常的节区头数据都被破坏了，因此应该这个so本身也被加过壳了，很多数据只有在动态运行时才会解开，所以直接使用动态的方法，先运行这个程序后，直接在内存中把这个so dump出来。</p>

<p>首先需要在输入框中随便输入些数据后，点击确定，保证用户输入数据执行到native方法里后再做dump。我们使用的方法是查看maps后，使用dd命令把整个so都dump出来。</p>

<p>输入命令：</p>

<pre><code><a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="5624393922163b3731232439">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>:/ # ps | grep crackme.a4
u0_a73    1935  126   512204 48276 ffffffff 400dc408 S crackme.a4
<a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="c4b6ababb084a9a5a3b1b6ab">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>:/ # cat /proc/1935/maps
5e0f2000-5e283000 r-xp 00000000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
5e283000-5e466000 r-xp 00000000 00:00 0 
5e466000-5e467000 rwxp 00000000 00:00 0 
5e467000-5e479000 rw-p 00000000 00:00 0
5e479000-5e490000 r-xp 00191000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
5e490000-5e491000 rwxp 001a8000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
5e491000-5e492000 rw-p 001a9000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
5e492000-5e493000 rwxp 001aa000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
5e493000-5e4c1000 rw-p 001ab000 103:04 741132    /data/app-lib/crackme.a4-1/libmobisec.so
</code></pre>

<p>使用dd命令将libmobisec.so的内存dump出来</p>

<pre><code><a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="5f2d30302b1f323e382a2d30">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>:/ # dd if=/proc/1935/mem of=/sdcard/alimsc4 skip=1578049536 ibs=1 count=3993600
</code></pre>

<p>dd命令使用的数字都是十进制的，skip就是<code>libmobisec.so</code>的起始地址，count是总长度。 为了让IDA还能够识别libmobisec里的libc函数，我们还需要把libc也载入到IDA中，libc就直接从system/lib里拖出来就行了。</p>

<pre><code>adb pull /system/lib/libc.so ./
</code></pre>

<p>用IDA先打开libc，调整好是在内存中的偏移即rebase program，再在load additional binary里载入dd出来的libmobisec.so，通过maps里的偏移后载入。接下来的任务就是在其中找到M\$j这个函数的地址。</p>

<p>一开始尝试直接在dd出来的ELF文件中找这个M\$j这个函数名，类似的名字会被处理成</p>

<pre><code>Java_ali_00024a_M_00024j
</code></pre>

<p>类似下图：</p>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205268772.png" alt="图1" /></p>

<p>不过我没找到这个<code>M\$j</code>这个名字，逆过JNI库的都知道，如果符号表里找不到这个函数名，说明在<code>JNI_Onload</code>的时候，使用<code>RegisterNatives</code>函数重新将一个JNI函数映射为Native函数了。</p>

<p>正当一筹莫展的时候，我再次想起了InDroid系统。在Dalvik中，每个方法都是一个Method的结构体，其中当这个方法是native的时候，Method的insns这个指针会指向native方法的起始地址。因此我们修改了下InDroid，让Dalvik在执行<code>M\$j</code>这个方法前，去打印了<code>M\$j</code>方法的<code>insns</code>指针。这时我们得到了一个指向另一片内存区域的值，既不在libdvm中，也不在libmobisec中，并且这片内存页被映射成了rwx，由此推断里面也极有可能是代码，我们继而又dd出了这块内存，用IDA打开，使用ARM平台反汇编，发现该处就一条指令，是LOAD PC到另一个地址，而这个地址恰好在libmobisec中。于是我们直接到IDA中跳到这个地址，发现正好是个压栈指令，印证了我们的想法，此处就是M$j函数，于是在在IDA里该地址指令处，右击选择create function，让IDA识别这一段汇编指令为函数指令后，就可以通过F5查看看反编译的C代码了。</p>

<p>这个函数本身做了一些控制流混淆，同时还有很多字符串加解密的功能函数，一些简单的如异或操作，也被展开成与和或的组合等更长更复杂的表达式形式。另外还看到一些变形过的RC4，等等。不过因为我们已经是dump出来执行过的数据，所以必要的数据都已经解密了。如下图：</p>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205329764.png" alt="图2" /></p>

<p>通过查看反编译的C代码，我发现程序中是直接通过JNI方法调用了Java中的<code>bh</code>类的方法<code>a</code>（在图2常量中也可以看到）。 再次回到dex层查看<code>a</code>方法，该方法是不断的将输入传递给不同的函数进行处理，先是<code>cd</code>的<code>a</code>方法，<code>cC</code>的<code>a</code>方法，<code>p</code>的<code>a</code>方法，<code>x</code>的<code>a</code>方法，<code>ali$a</code>的<code>M$d</code>方法（native），<code>aS</code>的<code>a</code>方法，<code>x</code>的<code>a</code>方法，<code>ali$a</code>的<code>M&amp;z</code>方法（native），<code>cd</code>的<code>a</code>方法，<code>cC</code>的<code>a</code>方法，每一个方法都是些简单的数学运算，编码，以及密码学处理等可逆的操作，结合逆向和Indroid对输入输出的监控，都可以轻松确定每个Java函数的作用，具体过程如下代码显示：</p>

<pre><code>invoke-static {}, LbKn;.a:()Z // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="345951405c5b5074040c5505">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result v3
invoke-static {v3}, LbKn;.b:(I)V // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="630e06170b0c0723535b0251">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
add-int/lit8 v0, v5, #int 1 // #01
invoke-static {v4, v5}, Lcd;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="1e737b6a76717a5e2e7c2c2d">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v1
add-int/lit8 v2, v0, #int 1 // #01
invoke-static {v1, v0}, LcC;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="e08d8594888f84a0d081d3d0">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v1, v2, #int -1 // #ff
invoke-static {v0, v2}, Lp;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="fa979f8e92959ebaca9fc29e">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
invoke-static {v0, v1}, Lx;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="137e76677b7c775323767776">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v2, v1, #int -1 // #ff
invoke-static {v0, v1}, Lali$a;.M$d:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="69040c1d01060d29595a0d5a">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v1, v2, #int 1 // #01
invoke-static {v0, v2}, LaS;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="e78a82938f8883a7d7d5d582">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
invoke-static {v0, v1}, Lx;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="076a62736f68634737626362">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v2, v1, #int 1 // #01
invoke-static {v0, v1}, Lali$a;.M$z:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="84e9e1f0ecebe0c4b4b0b0b4">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v1, v2, #int 1 // #01
invoke-static {v0, v2}, Lcd;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="254840514d4a416515471716">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
add-int/lit8 v2, v1, #int 1 // #01
invoke-static {v0, v1}, LcC;.a:([BI)[B // <a class="__cf_email__" href="/cdn-cgi/l/email-protection" data-cfemail="2a474f5e42454e6a1a4b191a">[email&#160;protected]</a><script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script>
move-result-object v0
return-object v0
</code></pre>

<p>值得注意的是，其中有两个native的方法，因为InDroid还可以监控调用native方法的参数以及返回值，我们发现这几个native都没有对输入做复杂的处理，只有M\$d对输入的第四个字节做了减8的处理。</p>

<p>做了这些逆变换以后我们其实并没有找到最终比较的处理，不过在解密过的数据中（图2），不仅有之前需要调用的各种方法和类，还可以发现有个十分可疑的Base64的字符串。</p>

<pre><code>aJTCZnf6NyBPYJfbrBuLu0wOhRFbPtvqpYjiby5J81M=
</code></pre>

<p>并且在native的M\$z方法的反汇编代码中，可以看到有对这个Base64字符串的长度比较，由于我们并没有找到真正的比较函数，因此得到这个字符串后，我们直接从M\$z开始向上逆推之前的变换就得到了的答案。</p>

<p>具体解密代码如下：</p>

<pre><code>#!python
#!/usr/bin/env python
# encoding: utf-8

from Crypto.Cipher import AES

def Lcda(s):
    return ''.join(map(lambda x: chr((ord(x) + 3) &amp; 0xff), s))
def de_Lcda(s):
    return ''.join(map(lambda x: chr((ord(x) - 3) &amp; 0xff), s))

def LcCa(s, a):
    return ''.join([chr(((ord(s[i]) ^ a) + i) &amp; 0xff) for i in xrange(len(s))])
def de_LcCa(s, a):
    return ''.join([chr(((ord(s[i]) - i) &amp; 0xff) ^ a) for i in xrange(len(s))])

def Lpa(s):
    return s[1:] + s[0]
def de_Lpa(s):
    return s[-1] + s[:-1]

def Lxa(s):
    return s.encode("base64")[:-1]
def de_Lxa(s):
    return s.decode("base64")

def LaliaMd(s):
    return s[:3] + chr((ord(s[3]) - 8) &amp; 0xff) + s[4:]
def de_LaliaMd(s):
    return s[:3] + chr((ord(s[3]) + 8) &amp; 0xff) + s[4:]

def LaSa(s):
    BS = 16
    pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS)
    cc = AES.new("qqVJwt11yyLm7hVK1iI2aw==".decode("base64"), AES.MODE_ECB)
    cipher = cc.encrypt(pad(s))
    return cipher
def de_LaSa(s):
    cc = AES.new("qqVJwt11yyLm7hVK1iI2aw==".decode("base64"), AES.MODE_ECB)
    cipher = cc.decrypt(s)
    return cipher

res = "aJTCZnf6NyBPYJfbrBuLu0wOhRFbPtvqpYjiby5J81M="

flag = de_Lcda(de_LcCa(de_Lpa(de_Lxa(de_LaliaMd(de_LaSa(de_Lxa(res))))), 49))
print flag
</code></pre>

<p>结果为：</p>

<pre><code>alilaba2345ba
</code></pre>

<p>这里还需要提一下如何寻找<code>M\$d</code>和<code>M\$z</code>两个函数在so库中的地址的方法，不过这个方法是一些经验的总结，原因是整个native ELF文件的节区结构是被修改过的。这两个方法和M\$j不太一样，因为在dump出的libmobisec里可以找到M\$z的函数名，证明这个方法没有使用<code>RegiterNatives</code>来做变换，因此我们可以通过符号表来找这个函数与文件头部的偏移。方法是找<code>M\$z</code>和字符串表的偏移，如0x03FE，然后穷搜整个文件:</p>

<p><img src="http://static.wooyun.org/drops/20150330/2015033008205373783.png" alt="图3" /></p>

<p>因为符号表应该会把字符串表偏移作为一项，这块区域的结构体，我们对照ELF结构发现并不是标准的符号表，但还是可以大概看出结构体的内容，包括索引，字符串表偏移，以及ELF特殊的标志数，因此推测0x57BE4偏移是<code>M\$z</code>函数。该地址也正好是个压栈的指令，证明了我们的猜想。</p>

<h1>第五题</h1>

<hr />

<p><img src="http://static.wooyun.org/drops/20150331/2015033108563984733.png" alt="enter image description here" /></p>

<p><a href="http://drops.wooyun.org/wp-content/uploads/2015/03/AliCrackme_5.zip">题目下载</a></p>

<p>2015年移动安全挑战赛的最后一道题目，在规定的比赛时间内，仅有来自我们<a href="http://loccs.sjtu.edu.cn/gossip">GoSSIP</a>的wbyang一名选手解决了这道问题，今天我们就来揭开这一道最高难度题目的神秘面纱。</p>

<p>先把名为<code>AliCrackme_5.apk</code>的文件丢到JEB里看一看：</p>

<p><img src="http://static.wooyun.org/drops/20150331/2015033108564190995.jpg" alt="enter image description here" /></p>

<p>dex文件并没有进行加壳和混淆，看上去是一个非常简单的程序，Java代码部分使用函数<code>Register("Bomb_Atlantis", input)</code>对输入进行判断。所以需要分析的逻辑应该都在<code>libcrackme.so</code>里的<code>Register</code>函数中。</p>

<p>接下来我们用IDA打开这个<code>libcrackme.so</code>，不出所料的发现IDA完全没法处理，应该是进行了强烈的混淆和加壳处理：</p>

<p><img src="http://static.wooyun.org/drops/20150331/2015033108564388860.jpg" alt="enter image description here" /></p>

<p>使用和解决前面题目相同的技巧，我们继续使用<code>dd</code>的方法来去处一部分的混淆和加壳。运行一次程序后，从<code>/proc/self/maps</code>里找到<code>libcrackme.so</code>在内存中的位置，使用<code>dd</code>命令从<code>/proc/self/mem</code>中提取出内存中的<code>libcrackme.so</code>，接着使用在解决第四题时使用过的技巧，将<code>libcrackme.so</code>和<code>libc.so</code>一起加载到IDA里。</p>

<p>用IDA打开dump出的代码后，我们发现仍然有大部分的代码无法被IDA识别，需要手动定位到需要分析的代码然后手工定义（IDA快捷键<strong>C</strong>）代码，同时由于代码会在THUMB指令集和ARM指令集之间切换，有时候需要用快捷键<strong>ALT+G</strong>来将T寄存器设置为不同的值，设置正确后才能正确翻译出代码。这里我们首先遇到的问题是无法定位<code>Register</code>函数，同样使用第四题中的技巧，用InDroid监控到<code>Register</code>函数的真实地址，就可以在该地址上开始分析。</p>

<p>在<code>libcrackme.so</code>这个动态库里使用的一些混淆方法，对于处理了前面一些类似混淆后现在的我们来说已经不是问题（^&#95;^）。通过分析代码，我们定位了几个函数，这些函数的偏移在不同的设备上应该是不同的。整体的逻辑其实并不复杂，首先会有一个固定的字符串“Bomb&#95;Atlantis”和一个固定的salt去进行一次md5运算，salt是动态生成的，不过由于dump内存的时候这些动态的值已经生成好了，所以能够直接发现这个salt(出于一些版权原因我们不便公布本题目的一些内部细节，因此该salt值请大家自己分析）</p>

<p>之后程序会将这个md5值和我们的输入进行一些异或和计算的操作，经过几步比较简单、可逆的变换之后，进入一个比较复杂的函数，经过这个函数处理后直接和一个内存中的值进行比较，返回比较结果。</p>

<p><img src="http://static.wooyun.org/drops/20150331/2015033108564681128.jpg" alt="enter image description here" /></p>

<p>这里说一个我们在做第五题时用到的分析方法——动态hook。由于<code>libcrackme.so</code>中并没有对调用自身的上层应用进行验证，这就导致了我们可以自己写一个程序去加载这个so，调用其中的方法。这也导致了我们在加载<code>libcrackme.so</code>后，可以加载另一个用于hook的so，这样我们可以hook <code>libcrackme.so</code>中的任意函数，从而知道任意函数的参数和返回值，这对于我们理解程序有着非常大的帮助。这里我们使用的hook框架是著名Android安全研究人员Collin Mulliner开发的Android平台上的一个二进制注入框架<a href="https://github.com/crmulliner/adbi">adbi</a>。当然这道题目并不能够通过注入的方法将我们的so注入进去，因为源程序禁掉了ptrace这样的系统调用。我们对adbi稍作修改，使之成为一个可以手动加载的动态hook框架。同时由于我们没法通过符号表来定位函数的地址，所有的hook地址都需要硬编码，并且要和运行这道题目程序的Android设备内存映射严格对应。</p>

<p>需要指出的是adbi中存在一个小bug，<code>hook.c</code>这个文件的118行应该是</p>

<pre><code>h-&gt;jumpt[0]=0x60
</code></pre>

<p>而不是0x30，对应的thumb汇编应该是</p>

<pre><code>push{r5,r6}
</code></pre>

<p>而不是</p>

<pre><code>push{r4,r5}，
</code></pre>

<p>这个小bug在解题过程中会造成一些影响。使用adbi来hook这道题目的函数还需要注意一点，这题的代码中有一些函数使用的THUMB指令集，hook这些函数时，不要忘记人工的对hook地址+1。</p>

<p>通过hook的方法，我们已经能够动态的分析<code>libcrackme.so</code>，首先我们验证了我们对之前几步变换的分析结果。之后就是分析最后一个复杂的处理函数，通过<strong>静态分析+动态调试</strong>，我们发现这是一个类似于白盒密码学的加密函数。我们的输入进入函数后，首先经过几步类似DES的预处理，之后会进行若干轮的查表，通过查询一个巨大的表将我们的输入进行某种加密，生成一段密文，再经过几次简单的处理后和最后内存中的一段常量(出于一些版权原因我们不便公布本题目的一些内部细节，因此该常量请大家自己分析）进行比较。</p>

<p>通过动态调试，我们能够计算出加密算法最后应该输出的值，但是由于这个加密算法的密钥融入了整个置换表中，要找出一个逆置换表显然不太可能。我们简单过滤了<code>libcrackme.so</code>的其他函数，也没有发现用于解密的函数，想要正常解密密文是不太现实了。不过根据对加密算法的分析，我们发现这若干轮的置换是相互独立的，并且每一轮的复杂度并不高，这就意味这我们可以在可以接受的时间内对算法进行爆破。我们一开始的想法是code reuse，直接在Android设备上爆破，但是发现速度太慢，最后只能用笨办法，通过hook从内存中dump出来置换表，用C代码重写了这个算法，有惊无险地在比赛结束前半小时搜索出结果。根据逆推算法推出正确输入是：</p>

<pre><code>3EFoAdTxepVcVtGgdVDB6AA=   
</code></pre>

<p>好了，我们的2015移动安全挑战赛全系列回顾就到此为止了！希望大家能和我们多多交流讨论，欢迎大家关注我们的微博<strong>GoSSIP_SJTU</strong>，基本上每天都会有精彩的内容发布哦。</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          